package org.example.myleet.p517;

public class Solution {
    /**
     * https://leetcode-cn.com/problems/super-washing-machines/solution/chao-ji-xi-yi-ji-by-leetcode-solution-yhej/
     * 官方思路：
     * 将前 i 台洗衣机看成一组，记作 A，其余洗衣机看成另一组，记作 B。
     * 若 A的和是正说明要 向 B 移入sum[i]衣服，为负则说明需要从 B 向 A 移入sum[i]衣服。
     * 我们分两种情况来考虑操作步数：
     * 1、A 与 B 两组之间的衣服，最多需要 ∣sum[i]∣ 次衣服移动；
     * 2、组内的某一台洗衣机内的衣服数量过多，需要向左右两侧移出衣服，这最多需要 max(machines[i]−avg) 次衣服移动。
     */
    public int findMinMoves(int[] machines) {
        int tot = 0;
        for (int machine : machines) {
            tot += machine;
        }
        int n = machines.length;
        if (tot % n != 0) {
            return -1;
        }
        int avg = tot / n;
        int ans = 0, sum = 0;
        for (int num : machines) {
            num -= avg;
            sum += num;
            ans = Math.max(ans, Math.max(Math.abs(sum), num));
        }
        return ans;
    }
}
